package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-06 16:48
 */
public class 题库_0078_子集 {

  static
  class Solution {
    public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> answers = new ArrayList<>();
      backtrack(answers, 0, new boolean[nums.length], nums);
      return answers;
    }

    /**
     * 从 nums 本身考虑，针对每个数字都有 取 与 不取 两种状态
     * @param answers
     * @param index
     * @param mark
     * @param nums
     */
    private void backtrack(List<List<Integer>> answers, int index, boolean[] mark, int[] nums) {
      if (index == mark.length) {
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
          if (mark[i]) {
            answer.add(nums[i]);
          }
        }
        answers.add(answer);
        return;
      }

      // 要当前位置的数
      mark[index] = true;
      backtrack(answers, index + 1, mark, nums);

      // 不要当前位置的数
      mark[index] = false;
      backtrack(answers, index + 1, mark, nums);
    }

    public List<List<Integer>> subsets1(int[] nums) {
      List<List<Integer>> answers = new ArrayList<>();
      List<Integer> cur = new ArrayList<>();
      answers.add(cur);

      helper(answers, cur, 0, nums);
      return answers;
    }

    /**
     * 由 [] 向外扩展
     */
    private void helper(List<List<Integer>> answers, List<Integer> cur, int index, int[] nums) {
      if (index >= nums.length) {
        return;
      }

      for (int i = index; i < nums.length; ++i) {
        List<Integer> temp = new ArrayList<>(cur);
        temp.add(nums[i]);
        answers.add(temp);

        helper(answers, new ArrayList<>(temp), i + 1, nums);
      }
    }
  }

}
